package acwing._2LanQiao.test;
/**
 * @Project : AlgorithmLearning
 * @Package : ACWing._2LanQiao.test
 * @File : BFSDFS.java
 * @Author : WangRuoyu
 * @Date : 2023/4/7 17:00
 */

import java.io.*;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class BFSDFS {

    static int n;
    static int[] h;
    static int[] e;
    static int[] next;
    static int[] degree;
    static int[] tall;
    static int[] depth;
    static boolean[] st;
    static int idx = 0;

    static void add(int a, int b) {
        e[idx] = b;
        next[idx] = h[a];
        h[a] = idx++;
    }

    static void dfsTravel(int x) {
        System.out.print(x + " ");
        st[x] = true;
        for (int i = h[x]; i != -1; i = next[i]) {
            int j = e[i];
            if (!st[j]) {
                dfsTravel(j);
            }
        }
    }

    static void bfsTravel(int x) {
        Queue<Integer> q = new LinkedList<>();
        q.add(x);
        st[x] = true;
        while (!q.isEmpty()) {
            int p = q.poll();
            System.out.print(p + " ");
            for (int i = h[p]; i != -1; i = next[i]) {
                int j = e[i];
                if (!st[j]) {
                    q.add(j);
                    st[j] = true;
                }
            }
        }
    }

    static void dfsDepth(int x, int father) {
        if (x == 1) {
            depth[x] = 1;
        } else {
            depth[x] = depth[father] + 1;
        }

        for (int i = h[x]; i != -1; i = next[i]) {
            int j = e[i];
            if (j != father) {
                dfsDepth(j, x);
            }
        }
    }

    static int dfsTall(int x, int father) {
        if (degree[x] == 1 && x != 1) {
            tall[x] = 1;
            return 1;
        }
        int t = 0;
        for (int i = h[x]; i != -1; i = next[i]) {
            int j = e[i];
            if (j != father) {
                if (tall[j] > 0) {
                    t = Math.max(tall[j] + 1, t);
                } else {
                    t = Math.max(dfsTall(j, x) + 1, t);
                }
            }
        }
        tall[x] = t;
        return t;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = 9;
        h = new int[n + 1];
        degree = new int[n + 1];
        tall = new int[n + 1];
        depth = new int[n + 1];
        Arrays.fill(h, -1);
        e = new int[2 * n + 10];
        next = new int[2 * n + 10];
        st = new boolean[n + 1];
        for (int i = 0; i < n - 1; ++i) {
            String[] words = br.readLine().split(" ");
            int a = Integer.parseInt(words[0]);
            int b = Integer.parseInt(words[1]);
            add(a, b);
            add(b, a);
            degree[a]++;
            degree[b]++;
        }
        // 深搜遍历
        dfsTravel(1);
        System.out.println();
        Arrays.fill(st, false);
        // 宽搜遍历
        bfsTravel(1);
        System.out.println();
        Arrays.fill(st, false);
        // 深搜查高度
        dfsTall(1, -2);
        for (int i = 1; i <= n; ++i) {
            System.out.print(tall[i] + " ");
        }
        System.out.println();
        // 深搜查深度
        dfsDepth(1, -2);
        for (int i = 1; i <= n; ++i) {
            System.out.print(depth[i] + " ");
        }
    }
}

//1 2
//1 3
//2 4
//2 5
//3 6
//3 7
//4 8
//4 9